# -*- coding: utf-8 -*-

"""剑指 Offer II 083. 没有重复元素集合的全排列
给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：
输入：nums = [1]
输出：[[1]]

提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同"""


class Solution:
    """从池子中遍历所有元素，更新分组，构建删除相应元素的新池子，进入下一回
    回溯+递归
    池子需要支持遍历，按值删除，用哈希表"""
    def permute(self, nums):
        answer, pool = [], set(nums)
        def fork(pool, group):
            if not pool:
                answer.append(group)
                return
            
            for n in pool:
                pool_new = pool.copy()
                group_new = group.copy()
                group_new.append(n)
                pool_new.remove(n)
                fork(pool_new, group_new)
        fork(pool, [])
        return answer


if __name__ == '__main__':
    so = Solution()
    print(so.permute([1,2,3]))
    print(so.permute([0,1]))
    print(so.permute([1]))
